#include "param.h"
#include "fs.h"
#include "file.h"
#include "spinlock.h"
#include "sleeplock.h"
#include "defs.h"

#define min(a, b)   ((a) < (b) ? (a) : (b))
struct superblock sb;

void print_disk_inode(struct dinode * di) {
    printf("dinode, type:%d[1:dir,2:file,3-device], nlink:%d, size:%u\n", di->type, di->nlink, di->size); 

    if(di->size > 0){
      printf("\t");
      for(int i = 0; i <= NDIRECT; ++i){
        printf("[%d]:%d,", i, di->addrs[i]);
      }
      printf("\n");

      if(di->size > BSIZE * NDIRECT){
        printf("\t\t[%d]:%d -> ", NDIRECT, di->addrs[NDIRECT]);
        struct buf * b = bread(ROOTDEV, di->addrs[NDIRECT]);
        for(int i = 0; i < BSIZE/sizeof(uint); ++i){
          printf("[%d]:%u,", NDIRECT + i, ((uint*)(b->data))[i]);
        }
        brelse(b);
        printf("\n");
      }
    }
}
//TODO: DEBUG 
//void print_mem_inode(inum) {
//}
// print_inodes()
// print_bitmaps()
// print_dirents(struct inode* ip)


static void readsb(uint dev, struct superblock * sb) {
  struct buf * b = bread(dev, 1);
  memmove(sb, b->data, sizeof(struct superblock));
  brelse(b);
}

void sb_print() {
  printf("super block:\n");
  printf("\tmagic:      0x%x\n", sb.magic);
  printf("\tsize:       %8u -- size of file system imags (blocks)\n", sb.size);
  printf("\tnblocks:    %8u  -- number of data (blocks)\n", sb.nblocks);
  printf("\tninodes:    %8u -- number of inodes\n", sb.ninodes);
  printf("\tnlog:       %8u -- number of log (blocks)\n", sb.nlog);
  printf("\tlogstart:   %8u -- blockno of first log block (log header)\n",sb.logstart);
  printf("\tinodestart: %8u -- blockno of first inode block\n", sb.inodestart);
  printf("\tbmapstart:  %8u -- blockno of first free map block\n", sb.bmapstart);
}

void fsinit(uint dev) {
  readsb(dev, &sb);
#ifdef DEBUG
  sb_print();
#endif

  if(sb.magic != FSMAGIC)
    panic("invalid file system");
  initlog(dev, sb.logstart, sb.nlog);
}

struct {
  struct spinlock lock;
  struct inode inode[NINODE];
} itable;

void iinit(void) {
  initlock(&itable.lock, "itable");
  for(int i = 0; i < NINODE; i++) {
    initsleeplock(&itable.inode[i].lock, "inode");
  }
}

// inode usage
//  struct inode * ip = iget(dev, inum);
//  ilock(ip);
//  .... modify ip->xxx;
//  iunlock(ip);
//  iput(ip)

static struct inode * iget(uint dev, uint inum);
//alloc an empty node in dev, 
//and mapping to an empty mem inode
struct inode * ialloc(uint dev, short type){
  // i = 1 because of (ROOTINO == 1)
  for(int i = 1; i < sb.ninodes; ++i){
    struct buf * b = bread(dev, IBLOCK(i, sb));
    struct dinode * di = (struct dinode*)b->data + i % IPB;
    if(di->type == 0) {
      memset(di, 0, sizeof(*di));
      di->type = di->type;
      log_write(b);
      brelse(b);
      return iget(dev, i);
    }
    brelse(b);
  }
  printf("ialloc: no inodes\n");
  return 0;
}

struct inode * iget(uint dev, uint inum){
  acquire(&itable.lock);
  struct inode * empty;
  for(struct inode * ip = itable.inode; ip < &itable.inode[NINODE]; ip++){
    if(ip->ref > 0  && ip->dev == dev && ip->inum == inum) {
      ip->ref ++;
      release(&itable.lock);
      return ip;
    }
    if(ip->ref == 0 && empty == 0){
      empty = ip;
    }
  }

  if(empty == 0)
    panic("iget: no free inode in memory cache");

  empty->dev = dev;
  empty->inum = inum;
  empty->ref = 1;
  empty->valid = 0;
  release(&itable.lock);

  return empty;
}

//write inode values to  memory dinode values
//memory -> disk
void iupdate(struct inode * ip) {
  struct buf * b = bread(ip->dev, IBLOCK(ip->inum, sb));
  struct dinode * di = (struct dinode*)b->data + ip->inum % IPB;
  di->type = ip->type;
  di->major = ip->major;
  di->minor = ip->minor;
  di->nlink = ip->nlink;
  di->size = ip->size;
  memmove(di->addrs, ip->addrs, sizeof(ip->addrs));
  log_write(b);
  brelse(b);
}

//read inode values from disk dinode values, and locked the inode
//disk --> memory
void ilock(struct inode * ip){

  if(ip == 0 || ip->ref < 1) 
    panic("ilock");

  acquiresleep(&ip->lock);

  if(ip->valid == 0){
    struct buf * b = bread(ip->dev, IBLOCK(ip->inum, sb));
    struct dinode * di = (struct dinode *)b->data + ip->inum % IPB;
    ip->type = di->type;
    ip->major = di->major;
    ip->minor = di->minor;
    ip->nlink = di->nlink;
    ip->size = di->size;
    memmove(ip->addrs, di->addrs, sizeof(ip->addrs));
    brelse(b);
    ip->valid = 1;
    if(ip->type == 0)
      panic("ilock: no type");
  }
}

void iunlock(struct inode * ip){
  if( ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1)
    panic("iunlock");
  releasesleep(&ip->lock);
}

static void _bzero(uint dev, uint blockno){
  struct buf * b = bread(dev, blockno); 
  memset(b->data, 0, BSIZE);
  log_write(b);
  brelse(b);
}
static int _balloc(uint dev){
  for(int bn = 0; bn < sb.size; bn += BPB){
    struct buf * b = bread(dev,  BBLOCK(bn, sb)); //bitmap block
    for(int bi = 0; bi < BPB && bn + bi < sb.size; bi ++ ){
      uint m = 1 << (bi % 8);
      if( (b->data[bi/8] &m) == 0){
        b->data[bi/8] |= m;
        log_write(b);
        brelse(b);
        _bzero(dev, bn + bi);
        return bn + bi;
      }
    }

    brelse(b);
  }
  return 0;
}
static void _bfree(uint dev, uint blockno){
  uint bi = blockno % BPB; // blockno in bblock
  uint m = 1 << (bi % 8); // offset in byte of block internal 

  struct buf * b = bread(dev, BBLOCK(blockno, sb));
  if((b->data[bi/8] &m ) == 0)
    panic("_bfree the free block");

  b->data[bi/8] &= ~m;
  log_write(b);
  brelse(b);
}

void itrunc(struct inode * ip){
  for(int i = 0; i < NDIRECT; ++i){
    if(ip->addrs[i]){
      _bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }

  if(ip->addrs[NDIRECT]){
    struct buf * b = bread(ip->dev, ip->addrs[NDIRECT]);

    uint * addr = (uint *)b->data;
    for( int j = 0; j < NINDRECT; ++j){
      if(addr[j]){
        _bfree(ip->dev, addr[j]);
        addr[j] = 0;
      }
    }

    brelse(b);

    _bfree(ip->dev, ip->addrs[NDIRECT]);
    ip->addrs[NDIRECT] = 0;
  }
  ip->size = 0;

  iupdate(ip);
}
//free disk inode & inode->addrs
void iput(struct inode * ip) {
  acquire(&itable.lock);
  
  if(ip->ref == 1 && ip->valid && ip->nlink == 0){
    acquiresleep(&ip->lock);
    release(&itable.lock);

    itrunc(ip);
    ip->type = 0;
    iupdate(ip);
    ip->valid = 0;
    releasesleep(&ip->lock);
    
    acquire(&itable.lock);
  }

  ip->ref--;
  release(&itable.lock);
}

void iunlockput(struct inode * ip){
  iunlock(ip);
  iput(ip);
}
struct inode * idup(struct inode * ip){
  acquire(&itable.lock);
  ip->ref ++;
  release(&itable.lock);
  return ip;
}

void stati(struct inode * ip, struct stat * st){
  st->dev = ip->dev;
  st->ino = ip->inum;
  st->type = ip->type;
  st->nlink = ip->nlink;
  st->size = ip->size;
}

//return disk blockno  according to inode && blockno-in-file
//alloc a block if inode->addrs..[blockno] == 0
static uint _bmap(struct inode * ip, uint blockno){
  if(blockno < NDIRECT) {
    if(ip->addrs[blockno] == 0){
      uint addr = _balloc(ip->dev);
      if(addr == 0)
        return 0;
      ip->addrs[blockno] = addr;
    }

    return ip->addrs[blockno];
  }
  blockno -= NDIRECT;

  if(blockno < NINDRECT){
    uint addr = ip->addrs[NDIRECT]; //inode addr-indirect table
    if(addr == 0){
      addr = _balloc(ip->dev);
      if(addr == 0)
        return 0;
      ip->addrs[NDIRECT] = addr;
    }
    
    struct buf * b = bread(ip->dev, addr);

    uint* a = (uint*)b->data;
    if( (addr = a[blockno]) == 0){
      addr = _balloc(ip->dev);
      if(addr == 0)
        return 0;
      a[blockno] = addr;
      log_write(b);
    }

    brelse(b);
    return 0;
  }
  
  panic("bmap: out of range");
}

//read ip[off:n] --to--> dst[0:n]    ;      
//if user_dst == 1 then dst in user space else in kernel space 
int readi(struct inode * ip, int user_dst, uint64 dst, uint off, uint n)
{
  if(off > ip->size || off + n < off)
    return 0;
  if(off +n > ip->size)
    n = ip->size - off;

  uint total = 0;
  uint m = 0;
  for(; total < n; total += m, off+=m, dst+=m) {
    uint addr = _bmap(ip, off/BSIZE);  //blockno
    if(addr == 0)
      break;
    struct buf * b = bread(ip->dev, addr);

    m = min(n - total, BSIZE - off%BSIZE);
    if(either_copyout(user_dst, dst, b->data + (off % BSIZE), m) == -1){
      brelse(b);
      total = -1;
      break;
    }
    brelse(b);
  }
  return total;
}


//write src[off:n] -> inode[cur:n]
//if user_src == 1 then src in user space else in kernel space
int writei(struct inode * ip, int user_src, uint64 src, uint off, uint n)
{
  if(off > ip->size || off + n < off)
    return -1;
  if(off + n > MAXFILE * BSIZE)
    return -1;

  int total = 0;
  uint m = 0;
  for(; total <n; total += m, off+= m, src+=m){
    uint addr = _bmap(ip, off/BSIZE);
    if(addr == 0)
      break;
    struct buf * b = bread(ip->dev, addr);
    m = min(n - total, BSIZE - off/BSIZE);
    if(either_copyin(b->data + (off % BSIZE), user_src, src, m) == -1){
      brelse(b);
      break;
    }
    log_write(b);
    brelse(b);
  }

  if(off > ip->size)
    ip->size = off;

  iupdate(ip);

  return total;
}

//directory
int namecmp(const char * s, const char * t)
{
  return strncmp(s, t, DIRSIZE);
}

//    skipelem(/a/b/c)  -> path=b/c, name="a"
static const char * _skipelem(const char * path, char * name) {
  while(*path == '/')
    path ++;

  if(*path == 0)
    return 0;

  const char * s = path;
  while(*path != '/' && *path != 0)
    path++;
  int len = path -s ;
  if(len >= DIRSIZE)
    memmove(name, s, DIRSIZE);
  else {
    memmove(name, s, len);
    name[len] = 0;
  }
  while(*path == '/')
    path ++;

  return path;
}

struct inode * dirlookup(struct inode * dp, char * name, uint *poff)
{
  if(dp->type != T_DIR)
    panic("dirlookup not DIR");
  
  struct dirent de;
  for(int off = 0; off < dp->size; off += sizeof(de)) {
    if(readi(dp, 0, (uint64)&de, off, sizeof(de))  != sizeof(de))
      panic("dirlookup read");

    if(de.inum == 0) // de not valid
      continue;

    if(namecmp(name, de.name) == 0){
      if(poff)
        *poff = off;
      return iget(dp->dev, de.inum);
    }
  }
  return 0;
}

//   /a/b/c  --> find the  file[c] 's inode
struct inode * namei(const char * path) {
  struct inode * ip, * next;
  if(*path == '/')
    ip = iget(ROOTDEV, ROOTINO);
  else
    ip = iget(ROOTDEV, ROOTINO); //TODO: myproc().cwd;


  char name[DIRSIZE];
  while( (path = _skipelem(path, name)) != 0){
    ilock(ip);

    if(ip->type != T_DIR){ 
      iunlockput(ip);
      return 0;
    }

    if((next = dirlookup(ip, name, 0)) == 0){
      iunlockput(ip);
      return 0;
    }

    iunlockput(ip);
    ip = next;
  }

  return ip;
}



// "c" => return proc.cwd 's inode
// "a/b" =>  return  proc.cwd/a 's inode
struct inode * nameiparent(const char * path, char * name){
  struct inode * ip, * next;
  if(*path == '/')
    ip = iget(ROOTDEV, ROOTINO);
  else
    ip = iget(ROOTDEV, ROOTINO); //TODO: myproc().cwd;

  while( (path = _skipelem(path, name)) != 0){
    ilock(ip);
    if(ip->type != T_DIR){
      iunlockput(ip);
      return 0;
    }

    if(*path == '\0'){
      iunlock(ip);
      return ip;
    }

    if((next = dirlookup(ip, name, 0)) == 0){
      iunlockput(ip);
      return 0;
    }

    iunlockput(ip);
    ip = next;
  }
  iput(ip);
  return 0;
}

//create the name for dir inode(dp)
int dirlink(struct inode * dp, char * name, uint inum){
  struct inode * ip;
  // name is not present in dir(dp)
  if((ip = dirlookup(dp, name, 0)) != 0){
    iput(ip);
    return -1;
  }

  struct dirent de;
  int off = 0;
  for(; off < dp->size; off += sizeof(de)){
    if(readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
      panic("dirlink read");
    if(de.inum == 0)
      break;
  }

  strncpy(de.name, name, DIRSIZE);
  de.inum = inum;
  if(writei(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
    return -1;

  return 0;
}
